package com.example.algorithm.dp;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.EqualsAndHashCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yuzhenxin
 * @date 2023-07-16 15:14
 */
public class ThrowEggs {

    private static final Map<Tmp, Integer> memo = new HashMap<>();

    public static void main(String[] args) {
        int i = superEggDrop(3, 7);
        System.out.println(i);
    }

    /**
     * 高楼扔鸡蛋，扔多少次才能找到刚好不破的那一层（可能为0）
     *
     * @param k 鸡蛋数
     * @param n 楼层
     * @return 扔的最少次数
     */
    private static int superEggDrop(int k, int n) {
        if (k == 1) {
            // 一个鸡蛋，只能从第一层开始扔，扔n次
            return n;
        }
        // 没有楼层，不用扔
        if (n == 0) {
            return 0;
        }
        Tmp tmp = new Tmp(k, n);
        Integer integer = memo.get(tmp);
        if (integer != null) {
            return integer;
        }

        int res = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            res = Integer.min(res,
                    Integer.max(
                            // 没碎，往上找
                            superEggDrop(k, n - i),
                            // 碎了，往下找
                            superEggDrop(k - 1, i - 1)
                    ) + 1);
        }

        // 记录备忘录
        System.out.println("写入" + tmp + "：" + res);
        memo.put(tmp, res);

        return res;
    }

    @AllArgsConstructor
    @Data
    @EqualsAndHashCode
    private static class Tmp {
        private Integer k;
        private Integer n;
    }

}
